package com.czk.sort;

import java.util.Arrays;

/**
 * 快速排序的添加
 *
 * @Author:ChenZhangKun
 * @Date: 2020/6/29 20:49
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] array = {5, 4, 3, 2, 1};
        quickSort_1(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    public static void quickSort(int[] array, int left, int right) {
        int l = left; //左下标
        int r = right; // 右下标
        int pivot = array[(l + r) / 2]; // 中轴值
        // 比pivot大的值放在右边
        // 比pivot小的值放在左边
        while (l < r) {
            while (array[l] < pivot) {
                l += 1;
            }
            while (array[r] > pivot) {
                r -= 1;
            }
            // 说明pivot左右两边的值已经是按照顺序排列
            if (l > r) {
                break;
            }
            // 交换两边的值
            int temp = array[l];
            array[l] = array[r];
            array[r] = temp;
            if (array[r] == pivot) r--;
            if (array[l] == pivot) l++;
        }
        if (l == r) l++;
        r--;
        // 防止无限调用
        if (left < r) {
            // 左边排序
            quickSort(array, left, r);
        }
        if (right > l) {
            // 右边排序
            quickSort(array, l, right);
        }

    }

    public static void quickSort_1(int[] array, int left, int right) {
        int l = left;
        int r = right;
        // 拿到中间值
        int pivot = array[(l + r) / 2];
        while (l < r) {
            while (array[l] < pivot) {
                // 左指针往右移
                l++;
            }
            while (array[r] > pivot) {
                // 右指针左移
                r--;
            }
            if (l > r) break;
            // 交换值
            int temp = array[l];
            array[l] = array[r];
            array[r] = temp;
            // 再次比较
            if (array[l] == pivot) l++;
            if (array[r] == pivot) r--;
        }
        if (l == r) {
            l++;
            r--;
        }
        // 递归
        if (left < r) {
            quickSort_1(array, left, r);
        }
        if (l < right) {
            quickSort_1(array, l, right);
        }

    }
}
